你得知道题目下表是从 开始编号,那么每个棋子只能控制与它距离不大于 的行。
所以只需压当前这一行的状态,令 表示前 行棋子,第 的摆放状态为 的方案。
那么有转移:
转移需要保证 的两行棋子不冲突,这也是本题的难点。
首先可以处理摆放棋子后不能再摆棋子的位置的二进制。(其实就是输入的模板取反。)
- 判断两行是否冲突
-
找到第一行的所有 '1'
-
将 '1' 和 对齐后,如果第二行和不能再摆棋子的位置有重合部分则不合法。
同理用第二行判断第一行。
- 判断同行是否冲突
直接看成两行按上述方法比较。
注意第 位一定为 ,会误判为重合,直接减去就可以了。
因为转移是一样的,所以可以用矩阵加速这个过程。
可以通过预处理合法的行来降低时间,不过复杂度最坏还是
#include <cstdio>
#define uint unsigned int
const int MAXM = 6;
int n , m , p , k , ban[ 3 ];
int Cnt , rS[ ( 1 << MAXM ) + 1 ];
struct Matrix {
int n , m; uint a[ ( 1 << MAXM ) + 1 ][ ( 1 << MAXM ) + 1 ];
Matrix operator * ( const Matrix &oth ) const {
Matrix Ans = {}; Ans.n = n , Ans.m = oth.m;
for( int i = 1 ; i <= Ans.n ; i ++ )
for( int j = 1 ; j <= Ans.m ; j ++ )
for( int k = 1 ; k <= m ; k ++ )
Ans.a[ i ][ j ] += a[ i ][ k ] * oth.a[ k ][ j ];
return Ans;
}
Matrix Quick_pow( Matrix x , int po ) {
Matrix Ans = {}; Ans.n = x.n , Ans.m = x.m;
for( int i = 1 ; i <= x.n ; i ++ ) Ans.a[ i ][ i ] = 1;
for( ; po ; po >>= 1 , x = x * x )
if( po & 1 ) Ans = Ans * x;
return Ans;
}
}St , Trans , Ed;
bool check1( int S ) {
for( int i = 0 ; i < m ; i ++ )
if( ( S >> i ) & 1 ) {
if( i == k && ( S & ban[ 1 ] ^ ( 1 << k ) ) ) return 0;
if( i < k && ( ( S << ( k - i ) ) & ban[ 1 ] ^ ( 1 << k ) ) ) return 0;
if( i > k && ( ( S >> ( i - k ) ) & ban[ 1 ] ^ ( 1 << k ) ) ) return 0;
}
return 1;
}
bool check2( int S1 , int S2 ) {
for( int i = 0 ; i < m ; i ++ )
if( ( S1 >> i ) & 1 ) {
if( i <= k && ( ( S2 << ( k - i ) ) & ban[ 2 ] ) ) return 0;
if( i > k && ( ( S2 >> ( i - k ) ) & ban[ 2 ] ) ) return 0;
}
for( int i = 0 ; i < m ; i ++ )
if( ( S2 >> i ) & 1 ) {
if( i <= k && ( ( S1 << ( k - i ) ) & ban[ 0 ] ) ) return 0;
if( i > k && ( ( S1 >> ( i - k ) ) & ban[ 0 ] ) ) return 0;
}
return 1;
}
void InitS( ) {
for( int S = 0 ; S < 1 << m ; S ++ )
if( check1( S ) ) rS[ ++ Cnt ] = S;
}
int main( ) {
scanf("%d %d",&n,&m);
scanf("%d %d",&p,&k);
for( int i = 0 , x ; i < 3 ; i ++ )
for( int j = 0 ; j < p ; j ++ )
scanf("%d",&x) , ban[ i ] |= ( x << j );
InitS( );
St.n = 1 , St.m = Cnt;
St.a[ 1 ][ 1 ] = 1;
Trans.n = Trans.m = Cnt;
for( int i = 1 ; i <= Cnt ; i ++ )
for( int j = 1 ; j <= Cnt ; j ++ )
Trans.a[ i ][ j ] = check2( rS[ i ] , rS[ j ] );
Ed = St * Trans.Quick_pow( Trans , n );
uint Ans = 0;
for( int dS = 1 ; dS <= Cnt ; dS ++ )
Ans += Ed.a[ 1 ][ dS ];
printf("%u\n", Ans );
return 0;
}